import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            int count = map.getOrDefault(array[i], 0) + 1;
            map.put(array[i], count);
        }
        int v = 0;
        for (int i : map.keySet()) {
            if (map.get(i) > array.length / 2) {
                v = i;
            }

        }
        return v;
    }
}
